/*
 * Skeleton code for CSC 360, Spring 2012, Assignment #4.
 *
 * Copyright: 2012 Michael Zastre
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>

#define SCHEME_NONE 0
#define SCHEME_FIFO 1
#define SCHEME_LRU  2
int page_replacement_scheme = SCHEME_NONE;

#define TRUE 1
#define FALSE 0
#define PROGRESS_BAR_WIDTH 30
#define MAX_LINE_LEN 100

int size_of_frame = 0;  /* power of 2 */
int size_of_memory = 0; /* number of frames */

int initialize(void);
int finalize(void);
int output_report(void);
long resolve_address(long, int);
void error_resolve_address(long, int);

int page_faults = 0;
int mem_refs    = 0;
int swap_outs   = 0;
int swap_ins    = 0;
int next_spot	= 1;

struct page_table_entry *page_table = NULL;

struct page_table_entry {
	long page_num;
	int dirty;
	int free;
};

struct node_t{
        long page_num;
	long frame;
        struct node_t* next;
        struct node_t* prev;
};

typedef struct node_t node;

typedef struct linked_list_t{
	node* head;
	node* tail;
	int size;
}page_list;

page_list* list = NULL;

void list_init()
{
	list->head = list->tail = NULL;
	list->size = 0;
}

void add_to_lru_list(node* new_node, long page, long frame)
{
	new_node->page_num = page;
	new_node->frame = frame;
	new_node->next = NULL;
	if (list->size==0) list->head = new_node;
	else list->tail->next = new_node;
	list->tail = new_node;
}

int scan_lru_list(long page)
{
	//printf("Scanning list of size %d\n",list->size);
	if(list->size<=0) return -1;
	node* curr = list->head;
	int i;
	for (i=0;i<list->size;i++)
	{
	//	printf("list->size=%d\n", list->size);
	//	printf("i=%d\n",i);
	//	printf("curr->page = %ld\n",curr->page_num);
		if (curr->page_num == page) return i;
		if (curr->next==NULL) break;
		else curr = curr->next;
	}
	return -1;
}

void update_lru_list(long page, long frame)
{
	//printf("page=%ld, frame=%ld\n",page,frame);
	int position;
	if((position=scan_lru_list(page))==-1)
	{
		static node* new_node;
		new_node = (node*) malloc(sizeof(node));
		new_node->page_num = page;
		new_node->frame = frame;
		if (list->size==0) list->head = list->tail = new_node; 
		else list->tail->next = new_node;
		list->tail = new_node;
		list->tail->next = NULL;
		list->size += 1;
	//	printf("added page %ld\n",new_node->page_num);
	}
	else
	{
		int i;
	//	printf("position=%d\n",position);
		if (position==0 && list->size==1) return;
		else if (position==0 && list->size>1)
		{
			list->tail->next = list->head;
			list->head = list->head->next;
			list->tail = list->tail->next;
			list->tail->next = NULL;
		}
		else
		{
			node* temp = list->head;
			for (i=0;i<position-1;i++) temp = temp->next;
			list->tail->next = temp->next;
			list->tail = temp->next;
			temp->next = temp->next->next;
			list->tail->next = NULL;
		}
	}

}


long lru(long page, long size_of_frame, long offset)
{
	long effective, frame;
	int i;

	for (i=0;i<size_of_memory;i++)
	{
		if (page_table[i].page_num == list->head->page_num)
		{
			page_table[i].page_num = page;
			break;
		}
		
	}

	list->head->page_num = page;
	frame = i;
//	if (frame==0) frame =1;
	list->head->frame = frame;
	list->tail->next = list->head;
	list->tail = list->head;
	list->head = list->head->next;
	list->tail->next = NULL;
	swap_ins++;
	swap_outs++;
	effective = (frame << size_of_frame) | offset;
//	printf("frame=%ld, offset=%ld, effective=%ld\n",frame,offset,effective);
	return effective;
}

long fifo(long page, long size_of_frame, long offset)
{
	long effective;
	long frame;
	page_table[next_spot].page_num = page;
	frame = next_spot;
	//printf("frame=%ld\n",next_spot);
	next_spot = (next_spot+1) % (size_of_memory-1);	
	//if (next_spot==0) next_spot=1;
	swap_ins++;
	swap_outs++;
        effective = (frame << size_of_frame) | offset;
	//printf("effective = %ld\n", effective);
	return effective;
}

long resolve_address(long logical, int memwrite)
{
	int i;
	long page, frame;
	long offset;
	long mask = 0;
	long effective;

	/* Get the page and offset */
//	printf("logical =%ld\n",logical);
	page = (logical >> size_of_frame);
	for (i=0; i<size_of_frame; i++) {
		mask = mask << 1;
		mask |= 1;
	}
//	printf("Needs page %ld\n",page);
	offset = logical & mask;
//	printf("mask=%ld\n",mask);
//	printf("offset=%ld\n",offset);
	
	/* Find page in the inverted page table. */
	frame = -1;

	for ( i = 0; i < size_of_memory; i++) {
		if (!page_table[i].free && page_table[i].page_num == page) {
			frame = i;
	//		printf("list_size = %d\n", list->size);
			if(page_replacement_scheme == 2) update_lru_list(page,frame);
		 	break;
		}
	}
	

	/* If frame is not -1, then we can successfully resolve the
	 * address and return the result. */
	if (frame != -1) {
		effective = (frame << size_of_frame) | offset;
		return effective;
	}

	/* If we reach this point, there was a page fault. Find
	 * a free frame. */
	page_faults++;

	for ( i = 0; i < size_of_memory; i++) {
		if (page_table[i].free) {
			frame = i;
			if(page_replacement_scheme == 2) update_lru_list(page,frame);
			break;
		}
	}
	
	/* If we found a free frame, then patch up the
	 * page table entry and compute the effective
	 * address. Otherwise return 0 (i.e., no address
	 * should be zero, which is an error).
	 */
	if (frame != -1) {

		page_table[frame].page_num = page;
		page_table[i].free = FALSE;
		swap_ins++;
		effective = (frame << size_of_frame) | offset;
		return effective;
	} else {
		if (page_replacement_scheme==1) 
			return fifo(page,size_of_frame, offset);
		else if (page_replacement_scheme==2)
		{
			long rc = lru(page,size_of_frame, offset);
		//	printf("EFFECTIVE = %ld\n",rc);
			return rc;
		}
		//	return lru(page,size_of_frame, offset);
	}
	return -1;
}

void display_progress(int percent)
{
	int to_date = PROGRESS_BAR_WIDTH * percent / 100;
	static int last_to_date = 0;
	int i;

	if (last_to_date < to_date) {
		last_to_date = to_date;
	} else {
		return;
	}

	printf("Progress [");
	for (i=0; i<to_date; i++) {
		printf(".");
	}
	for (; i<PROGRESS_BAR_WIDTH; i++) {
		printf(" ");
	}
	printf("] %3d%%", percent);
	printf("\r");
	fflush(stdout);
}


int initialize()
{
	int i;
	list = (page_list*) malloc(size_of_memory * sizeof(struct linked_list_t));
	list->head = list->tail = NULL;
	list->size = 0;
	page_table = (struct page_table_entry *)malloc(sizeof(struct page_table_entry) * size_of_memory);

	if (page_table == NULL) {
		fprintf(stderr, "Simulator error: cannot allocate memory for page table.\n");
		exit(1);
	}

	for (i=0; i<size_of_memory; i++) {
		page_table[i].free = TRUE;
	}
	return 0;
}


int finalize()
{		
	free(list);
	free(page_table);
	return 0;
}


void error_resolve_address(long a, int l)
{
	fprintf(stderr, "\n");
	fprintf(stderr, "Simulator error: cannot resolve address 0x%lx at line %d\n",a, l);
	exit(1);
}


int output_report()
{
	printf("\n");
	printf("Memory references: %d\n", mem_refs);
	printf("Page faults: %d\n", page_faults);
	printf("Swap ins: %d\n", swap_ins);
	printf("Swap outs: %d\n", swap_outs);
	return 0;
}


int main(int argc, char **argv)
{
	int i;
	char *infile_name = NULL;
	struct stat infile_stat;
	FILE *infile = NULL;
	int infile_size = 0;
	char *s;
	int show_progress = FALSE;
	char buffer[MAX_LINE_LEN], is_write_c;
	long addr_inst, addr_operand;
	int  is_write;
	int line_num = 0;
//	list = (page_list*) malloc(sizeof(struct linked_list_t));

	for (i=1; i < argc; i++) {
		if (strncmp(argv[i], "--scheme=", 9) == 0) {
			s = strstr(argv[i], "=") + 1;
			if (strcmp(s, "fifo") == 0) {
				page_replacement_scheme = SCHEME_FIFO;
			} else if (strcmp(s, "lru") == 0) {
				page_replacement_scheme = SCHEME_LRU;
			}		
		} else if (strncmp(argv[i], "--file=", 7) == 0) {
			infile_name = strstr(argv[i], "=") + 1;
		} else if (strncmp(argv[i], "--framesize=", 12) == 0) {
			s = strstr(argv[i], "=") + 1;
			size_of_frame = atoi(s);
		} else if (strncmp(argv[i], "--numframes=", 12) == 0) {
			s = strstr(argv[i], "=") + 1;
			size_of_memory = atoi(s);
		} else if (strcmp(argv[i], "--progress") == 0) {
			show_progress = TRUE;
		}
	}

	if (infile_name == NULL) {
		infile = stdin;
	} else if (stat(infile_name, &infile_stat) == 0) {
		infile_size = (int)(infile_stat.st_size);
		infile = fopen(infile_name, "r");  /* If this fails, infile will be null */
	}


	if (page_replacement_scheme == SCHEME_NONE ||
	    size_of_frame <= 0 ||
	    size_of_memory <= 0 ||
	    infile == NULL)
	{
		fprintf(stderr, "usage: %s --framesize=<m> --numframes=<n>", argv[0]);
		fprintf(stderr, " --scheme={fifo|lru} [--file=<filename>]\n");
		exit(1);
	}


	initialize();

	while (fgets(buffer, MAX_LINE_LEN-1, infile)) {
		line_num++;
		if (strstr(buffer, ":")) {
			sscanf(buffer, "%lx: %c %lx", &addr_inst, &is_write_c, &addr_operand);

		 	if (is_write_c == 'R') {
				is_write = FALSE;
			} else if (is_write_c == 'W') {
				is_write = TRUE;
			}  else {
				fprintf(stderr, "Simulator error: unknown memory operation at line %d\n", line_num);
				exit(1);
			}
		/*	long rc;
			rc = resolve_address(addr_inst, FALSE);
			printf("first rc=%ld\n",rc);
			if (rc==-1) error_resolve_address(addr_inst, line_num);
			rc = resolve_address(addr_operand, is_write);
			printf("second rc=%ld\n",rc);
                        if (rc==-1) error_resolve_address(addr_inst, line_num);
		*/
			if (resolve_address(addr_inst, FALSE)==-1) {
				error_resolve_address(addr_inst, line_num);
			}
			if (resolve_address(addr_operand, is_write)==-1) {
				error_resolve_address(addr_operand, line_num);
			}
	
			mem_refs += 2;
		} else {
			sscanf(buffer, "%lx", &addr_inst);
			if (!resolve_address(addr_inst, FALSE)) {
				error_resolve_address(addr_inst, line_num);
			}
			mem_refs++;
		}

		if (show_progress) {
			display_progress(ftell(infile) * 100 / infile_size);
		}
	}
	

	finalize();
	output_report();

	fclose(infile);
	return 0;
}
